1. Field of the Invention
The present invention relates to a multiplier, and more particularly to a multiplier utilizing the Booth algorithm.
2. Description of the Prior Art
There has been known a high-speed multiplier which utilizes the Booth algorithm that is used as an arithmetic process for digital filters. See, for example, Digital Signal Processing, p. 145, published by the Electronic Communications Society.
A multiplication process based on the Booth algorithm will be described below.
It is assumed that a multiplicand is represented by X, a multiplier by Y, and the product of the multiplicand X and the multiplier Y by U. First, the multiplier Y is expressed by a series of multiplier codes represented by complements of 2 according to equation (1a), and the series of multiplier codes is replaced by a series of differential codes according to equation (1b). ##EQU1##
With y.sub.m+1 =0, equation (1b) can be rewritten as follows: ##EQU2##
Therefore, the product is given by: ##EQU3## A multiplication can be realized by repeating addition and shifted addition of the multiplicand X with codes y.sub.i, y.sub.i+1 as follows: ##EQU4##
When pairs of the terms of equation (2) are put together, equation (2) can be expressed by: ##EQU5## Multiplication expressed by complements of 2 based on the secondary Booth algorithm can thus be realized by adding and subtracting multiplicands X, 2X with codes y.sub.2i, y.sub.2i+1, y.sub.2i+2 as follows: ##EQU6##
If the multiplicand X and the multiplier Y are M- and N-bit numbers, respectively, in binary notation, then when the product of the coefficient relating to the degree of each 2.sup.m-2i-1 and the multiplicand X, i.e., the partial product, is positive, the complement of 2 representation is M+1 bits at maximum, but when the product is negative, the complement of 2 representation extends to an (M+N-1)th bit.
For example, if the multiplicand X is 15 and the multiplier Y is 55, then the product U is given according to equation (3) by: ##EQU7##
When the above calculation is expressed by binary notation, the partial product relating to the degree of each 2.sup.m-2i-1 is represented by: ##EQU8## As the degree of 2.sup.m-2i-1 is lower, the bits of a negative number extend to the high-order bit side, resulting in a need for a number of adders.
To prevent the bits from being thus extended, "1" is added to each of the Mth and (M+1)th bits, i.e., two high-order bits, of the complement of 2 representation, thereby converting the negative number into a positive number as follows: ##EQU9##
Therefore, since each partial product changes to a positive number, the bit is prevented from being extended to the high-order bit side, making it possible to reduce the number of adders required to calculate partial products.
In determining the sum of partial products which have been converted into positive numbers, inasmuch as "1" has been added to only the two high-order bits of each of the partial products for the conversion of the partial products into respective positive numbers, these sums are different from actual products. Therefore, it is necessary to correct for the conversion into positive numbers in the calculation of the sum.
The addition of "1" to the two high-order bits of each of the partial products for the conversion of the partial products into respective positive numbers results in the addition of "1" to all bits of the Mth and higher bits as counted from the low-order bit in the sum of converted partial products, i.e., the product. The "1" added to all bits of the sum can be removed to a carry by adding "1" to the other bits, i.e., all bits of the (M-1)th and lower bits., and finally adding "1" to the least significant position of the sum.
FIG. 1 of the accompanying drawings shows an arrangement for calculating a multiplication result with a conventional multiplier for determining the sum of partial products which have been converted into positive numbers. In FIG. 1, denoted at P00.about.P06, P10.about.P16, P20.about.P26, P30.about.P36 are partial products which have been converted into positive numbers, with P00, P10, P20, P30 representing respective least significant bits (LSBs) thereof and P06, P16, P26, P36 representing respective most significant bits (MSBs) thereof.
The multiplier includes adders 53 each for adding 1-bit inputs and outputting results S and carries C. Denoted at 54 is the sum of partial products, i.e., the product of a multiplier and a multiplicand, 52 is a carry which is produced from the sum 54 by a correction, and 50, 51 are corrective bits "1" to be added for a correction.
The partial products P00.about.P06, P10.about.P16, P20.about.P26, P30.about.P36 which have been converted into positive numbers are inputted to the adders 53 while they have been shifted two high-order bits corresponding to the degree of 2 based on the secondary Booth algorithm.
Since those bits to which "1" have been added by the conversion into positive numbers are P36, P35, P26, P25, P16, P15, P06, P05, as counted from the high-order bit, the corrective bit 50 of "1" is added to the other bits P04.about.P00, and their sum is determined.
If the partial products are negative before they are converted, then "1" is added as P0 negative, P1 negative, P2 negative, P3 negative to the respective least significant bits P00, P10, P20, P30 of the partial products which have been converted into positive numbers.
The corrective bit 51 of "1" is then added to the least significant bit of the sum thus determined to thereby correct for the conversion into positive numbers. If the carry 52 is produced, it is ignored. Since the carry 52 is ignored, the partial products become equivalent to those with nothing added thereto, and the product 54 of the multiplier and the multiplicand is outputted.
Because of the correction required for the conversion of the partial products into positive numbers, the conventional multiplier requires a number of adders which increase the circuit area needed for the multiplier in an entire LSI circuit and which also result in an increased power requirement and a lowered calculation speed.